package main.datastruc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树
 *
 * @author cyy
 */
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }

    /**
     * 创建完全二叉树
     *
     * @param nums 层序遍历顺序的数组
     * @return 二叉树根节点
     */
    public static TreeNode creCmpBTree(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        return helper(nums, 0);
    }

    private static TreeNode helper(int[] nums, int index) {
        if (index > nums.length - 1) {
            return null;
        }
        TreeNode root = new TreeNode(nums[index]);
        root.left = helper(nums, index * 2 + 1);
        root.right = helper(nums, index * 2 + 2);
        return root;
    }

    /**
     * 反序列化-创建二叉树
     *
     * @param data 序列化字符串才能
     * @return 二叉树根节点
     */
    public static TreeNode creCmpBTree(String data) {
        return deserialize(data);
    }

    private static TreeNode deserialize(String data) {
        String[] nums = data.split(",");
        if (nums.length == 0 || nums[0].isEmpty()) {
            return null;
        }
        List<String> list = new ArrayList<>(Arrays.asList(nums));
        return dfs(list);
    }

    /** 先序遍历 -- 递归 */
    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    /** 中序遍历 -- 递归 */
    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val);
        inOrder(root.right);
    }

    /** 后序遍历 -- 递归 */
    public static void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val);
    }

    /** 前序遍历 -- 非递归 */
    public static void preOrderII(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode node;
        while (!stack.isEmpty()) {
            node = stack.pop();
            System.out.print(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    /** 中序遍历 -- 非递归 */
    public static void inOrderII(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) { // 将左路存入栈中
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                System.out.print(node.val);
                node = node.right; // 转入右路
            }
        }
    }

    /** 后序遍历 -- 非递归（单栈实现） */
    public static void postOrderII(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        TreeNode tmp = null; // 标记已被访问过的右结点
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.peek();
                if (node.right != null && tmp != node.right) { // 有右孩子 且 未被访问过
                    node = node.right;
                } else {
                    tmp = stack.pop(); // 存储被访问的结点
                    System.out.print(node.val);
                    node = null;
                }
            }
        }
    }

    /**
     * 层序遍历
     *
     * @return
     */
    public static String levelOrderII(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode node;
        StringBuilder res = new StringBuilder();
        while (!queue.isEmpty()) {
            node = queue.remove();
            res.append(node.val).append(' ');
            if (node.left != null) {
                queue.add(node.left);
            } else {
                res.append("null ");
            }
            if (node.right != null) {
                queue.add(node.right);
            } else {
                res.append("null ");
            }
        }
        return res.toString();
    }

    /** 获取二叉树高度 */
    public static int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }

    /** 获取二叉树节点数 */
    public static int getNodesNum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + getNodesNum(root.left) + getNodesNum(root.right);
    }

    private static TreeNode dfs(List<String> data) {
        if ("null".equals(data.get(0))) {
            data.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(data.get(0)));
        data.remove(0);
        root.left = dfs(data);
        root.right = dfs(data);
        return root;
    }

    @Override
    public int hashCode() {
        return Objects.hash(val, left, right);
    }

    @Override
    public String toString() {
        return serialize(this);
    }

    private String serialize(TreeNode root) {
        StringBuilder res = new StringBuilder();
        if (root == null) {
            return res.toString();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode node;
        while (!queue.isEmpty()) {
            node = queue.poll();
            if (node == null) {
                res.append("null ");
                continue;
            }
            res.append(node.val).append(' ');
            queue.add(node.left);
            queue.add(node.right);
        }
        return res.toString();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (!(obj instanceof TreeNode)) {
            return false;
        }
        TreeNode node = (TreeNode) obj;
        return Objects.equals(val, node.val)
                && Objects.equals(left, node.left)
                && Objects.equals(right, node.right);
    }
}
